Network outages have significant economic and societal costs. While network operators have become adept at managing smaller failures, this is not the case for larger, regional failures such as natural disasters. Although it is not possible, and certainly not economic, to prevent all potential disaster damage and impact, we can reduce their impact by adding cost-efficient, geographically redundant, cable connections to the network. In this paper, we provide algorithms for finding cost-efficient, disaster-aware cable routes based on empirical hazard data. In contrast to previous work, our approach finds disaster-aware routes by considering the impact of a large set of input disasters on the network as a whole, as well as on the individual cable. For this, we propose the Disaster-Aware Network Augmentation Problem of finding a new cable connection that minimizes a function of disaster impact and cable cost. We prove that this problem is NP-hard and give an exact algorithm, as well as a heuristic, for solving it. Our algorithms are applicable to both planar and geographical coordinates. Using actual seismic hazard data, we demonstrate that by applying our algorithms, network operators can cost-efficiently raise the resilience of their network and future cable connections.

Several recent studies shed light on the vulnerability of networks against regional failures, which are failures of multiple nodes and links in a physical region due to a natural disaster. The paper defines a novel design framework, called Geometric Network Augmentation (GNA), which determines a set of node pairs and the new cable routes to be deployed between each of them to make the network always remain connected when a regional failure of a given size occurs. With the proposed GNA design framework, we provide mathematical analysis and efficient heuristic algorithms that are built on the latest computational geometry tools and combinatorial optimization techniques. Through extensive simulation, we demonstrate that augmentation with just a small number of new cable routes will achieve the desired resilience against all the considered regional failures.

While energy consumption is the primary concern for the design of real-time embedded systems, fault-tolerance and quality of service (QoS) are becoming increasingly important in the development of today's pervasive computing systems. In this work, we study the problem of energy-aware standby-sparing for weakly-hard real-time embedded systems. The standby-sparing systems adopt a primary processor and a spare processor to provide fault-tolerance for both permanent and transient faults. In order to reduce energy consumption for such kind of systems, we proposed two novel scheduling schemes: one for (1, 1)-hard tasks and one for general (m, k)-hard tasks which require that at least m out of any k consecutive jobs of a task meet their deadlines. Through extensive evaluations, our results demonstrate that the proposed techniques significantly outperform the previous research in reducing energy consumption for both (1, 1)-hard task sets and general (m, k)-hard task sets while assuring fault-tolerance through standby-sparing.

Proof of replication technique has been widely used to verify whether the cloud service providers (CSPs) store multiple replications of a file with dedicated and unique storage space, which effectively prevents CSPs from colluding and storing only one copy of the file. In this field, many representative schemes have been proposed and applied to various scenarios. However, most of the existing schemes are based on the timing assumption (i.e., the verifier rejects the proof of replication if the prover's response is timeout) and do not explicitly consider the problem of batch verification and fault localization. This will bring unnecessary computational overhead to the verifier and reduce the efficiency of batch auditing. To address the above problems, we propose a verifiable proof of replication scheme with fast fault localization and high efficiency. By integrating incompressible encoding and homomorphic linear authenticator, our scheme can effectively audit the integrity of file replications without timing assumptions. To support batch verification and fault localization, we propose a reversed signature aggregation tree (Rev-tree) by integrating the quick binary search and exponent testing. Compared with the traditional binary tree, Rev-tree can further reduce the overhead of batch verification and effectively locate a single fault replication. Moreover, benefit from the property of Rev-tree taking the existing error probability as an estimate of the rest of the tree, our scheme can adjust the verification strategy dynamically to meet with different situations. Finally, security analysis and experimental results show that our scheme is secure and efficient in proof of replication and fast fault localization.

NFV ecosystem is flourishing and more and more NF platforms appear, but this makes NF vendors difficult to deliver NFs rapidly to diverse platforms. We propose an NF development framework named NFD for cross-platform NF development. NFD's main idea is to decouple the functional logic from the platform logic -it provides a platform-independent language to program NFs' behavior models, and a compiler with interfaces to develop platform-specific plugins. By enabling a plugin on the compiler, various NF models would be compiled to executables integrated with the target platform. We prototype NFD, build 14 NFs, and support 6 platforms (standard Linux, OpenNetVM, GPU, SGX, DPDK, OpenNF). Our evaluation shows that NFD can save development workload for cross-platform NFs and output valid and performant NFs.

Network functions (NFs) are critical components in the network data plane. Their efficiency is important to the whole network's end-to-end performance. We identify three types of runtime redundant logic in individual NF and NF chains when they are deployed with concrete configured rules. We use program analysis techniques to optimize away the redundancy where we also overcome the NF specific challenges - we combine symbolic execution and dead code elimination to eliminate unused logic, we customize the common sub-expression elimination to eliminate duplicated logic, and we add network semantics to the dead code elimination to eliminate overwritten logic. We implement a prototype named NFReducer using LLVM. Our evaluation on both legacy and platform NFs shows that after eliminating the redundant logic, the packet processing rate of the NFs can be significantly improved and the operational overhead is small.

Locality Sensitive Hashing (LSH) is widely adopted to index similar data in high-dimensional space for approximate nearest neighbor search. With the rapid increase of datasets, recent interests in LSH have moved to the implementation of distributed search systems with low response time and high throughput. However, as the scale of the concurrent queries and the volume of available data grow, large amounts of index messages still need to be transmitted to centralized servers for the candidate answer reducing and resorting. Hence, the network remains the bottleneck in distributed search systems.

To address this gap, we turn our efforts to the network itself and propose NetSHa. NetSHa exploits the in-network computational capacity provided by programmable switches. Specially, NetSHa designs a sort-reduce approach to drop the potential poor candidate answers and aggregates the good candidate answers on programmable switches, while preserving the search quality. We implement NetSHa on Barefoot Tofino switches and evaluate it using 3 datasets (i.e., Random, Wiki and Image). The experimental results show that NetSHa reduces the packet volume by 10 times at most and improves the search efficiency by 3× at least, in comparison with typical LSH-based distributed search frameworks.

A modern network needs to conduct a diverse set of tasks, and the existing approaches focus on developing specific tools for specific tasks, resulting in increasing complexity and lacking reusability. In this paper, we propose Flow Algebra as a unifying, easy-to-use framework to accomplish a large set of network management tasks. Based on the observation that relational databases based on relational algebra are well understood and widely used as a unifying framework for data management, we develop flow algebra based on relational algebra. On the other hand, flow tables, which are the fundamental data specifying the state of a network, cannot be stored in traditional relations, because of fundamental features such as wildcard and priorities. We define flow algebra based on novel, generalized relational operations that use equivalency to achieve efficient, unifying data store, query, and manipulation of both flow tables and traditional relations. We realize flow algebra with FlowDB and demonstrate its ease of use on diverse tasks. We further demonstrate that generality and ease-of-use do not need to come with a performance penalty. For example, for the well-studied network verification task, our system outperforms two state-of-the-art network verification engines, NoD and HSA, in their targeted domain, by 55x.